//给你一个正整数 n ，开始时，它放在桌面上。在 10⁹ 天内，每天都要执行下述步骤：
//
//
// 对于出现在桌面上的每个数字 x ，找出符合 1 <= i <= n 且满足 x % i == 1 的所有数字 i 。
// 然后，将这些数字放在桌面上。
//
//
// 返回在 10⁹ 天之后，出现在桌面上的 不同 整数的数目。
//
// 注意：
//
//
// 一旦数字放在桌面上，则会一直保留直到结束。
// % 表示取余运算。例如，14 % 3 等于 2 。
//
//
//
//
// 示例 1：
//
//
//输入：n = 5
//输出：4
//解释：最开始，5 在桌面上。
//第二天，2 和 4 也出现在桌面上，因为 5 % 2 == 1 且 5 % 4 == 1 。
//再过一天 3 也出现在桌面上，因为 4 % 3 == 1 。
//在十亿天结束时，桌面上的不同数字有 2 、3 、4 、5 。
//
//
// 示例 2：
//
//
//输入：n = 3
//输出：2
//解释：
//因为 3 % 2 == 1 ，2 也出现在桌面上。
//在十亿天结束时，桌面上的不同数字只有两个：2 和 3 。
//
//
//
//
// 提示：
//
//
// 1 <= n <= 100
//
//
// Related Topics 数组 哈希表 数学 模拟 👍 53 👎 0

package leetcode.editor.cn;

import java.util.Arrays;

//java:统计桌面上的不同数字
public class Q2549CountDistinctNumbersOnBoard {
    public static void main(String[] args){
        Solution solution = new Q2549CountDistinctNumbersOnBoard().new Solution();
        solution.distinctIntegers(5);
    }
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int distinctIntegers(int n) {
//        int day = (int) 1e9;
        if(n < 1 || n > 100) return -1;
        // 保存1...n
        int[] arr = new int[n + 1];
        // 一开始n在桌面上
        arr[n] = 1;
        // 求n天，这个主要看数量
        for (int i = 0; i < n; i++) {
            // 罗列 1...n 的所有数字
            for (int j = 1; j <= n; j++) {
                // 剪枝操作
                if (arr[j] == 0) continue;
                for (int k = 1; k <= n; k++) {
                    if (arr[j] == 1) {
                        if (j % k == 1) {
                            arr[k] = 1;
                        }
                    }
                }
            }
        }
       return (int) Arrays.stream(arr).filter(i -> i == 1).count();
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}